<!DOCTYPE html>
<html>
	<head>
		<meta charset="UTF-8">
		<title>题五</title>
	</head>
	<body>
		<script>
			/*给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
			 * 示例 1：
			 * 输入: "babad"
			 * 输出: "bab"
			 * 注意: "aba"也是一个有效答案
			 * 示例 2：
			 * 输入: "cbbd"
			 * 输出: "bb"
			 * “回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
			 */
			function longestPalindrome(s){
				//思路：回文串特点：正序和逆序输出一样，如果将此字符串逆序输出，那么这两个字符串的公共子字符串即为最长回文串。
				 var i,j,l = 0,r = 0,ans = 1,len = s.length;
				 var dp=[]
    for(var i = 0; i < len; i++)
        dp[i][i] = 1;                //初始化
    for(i = len-1; i >= 0; i--){
        for(j = i+1; j < len; j++){
            if(s[i] == s[j]){
                if(i == j-1){
                    dp[i][j] = 1;
                }
                else{
                    dp[i][j] = dp[i+1][j-1];
                }
            }
            if(dp[i][j] == 1 && j-i+1 > ans){
                l = i;
                r = j;
                ans = j-i+1;
            }
        }
    }
    return s.substr(l,ans);
}
			var s="babad"
			console.log(longestPalindrome(s))
			
		</script>
	</body>
</html>
